The present invention relates to processors and, more particularly, to a processor having a parallel pipeline architecture designed especially to solve dynamic programming problems rapidly.
Dynamic programming provides a sequential decision-making approach for solving optimization problems. For example, the minimum fuel path of an aircraft between two locations often can be determined by using dynamic programming. In basic terms, dynamic programming converts a comparison of the many overall choices to select the optimum choice into a sequential comparison of much simpler intermediate optimization problems. In the aircraft example, the space (typically called a "state space") through which the aircraft can travel is divided into a multiple number of space volumes or cells. The optimum transitions from one cell to each of the adjacent ones closer to the end point is then calculated. The optimum transition may be dependent, for example, on the altitude and velocity of the aircraft.
The candidate optimum transitions of the aircraft from each and every one of the cells within which it can exist in the state space between the starting and end points are compared, and these optimum transitions are utilized to calculate the overall optimum path between the two points. Dynamic programming typically is carried out in reverse, i.e., by starting the calculations at the cell containing the end point and performing the calculations in reverse therefrom.
While the above example is based on the path of an aircraft between two points, dynamic programming is applicable to many other types of optimization problems in which a state space (not necessarily representative of physical space or volume) can be divided into cells. Manufacturing process control problems which can be characterized by a sequential solution of simpler intermediate optimization problems are also subject to dynamic programming solution. More details and specific explanations of dynamic programming can be found in the books entitled Applied Dynamic Programming by R. E. Bellman and S. E. Dreyfus, Princeton University Press (1962) and State Increment Dynamic Programming by R. E. Larson, American Elsevier Publishing Company, Inc., (1968) New York, N.Y.
While dynamic programming is a powerful tool for solving optimization problems, it has not found any significant usage in real-time applications in which solutions are required or desired relatively rapidly. For example, before the present invention, dynamic programming could not, as a practical matter, be used to determine the optimum path for a moving aircraft in real-time. The difficulty is that conventional digital computers on which such programs are solved are limited to serial solutions. It will be recognized that to solve a dynamic programming problem, it is necessary to serially make numerous computations, each one of which is dependent upon the results obtained in earlier comparisons. In any real-time situation, even with very fast processing speeds, it often takes more than a minute to obtain a solution. Again considering an aircraft, if an optimum path to some location from an aircraft's present position was chosen by a dynamic programming solution using conventional techniques, by the time the solution was obtained, the aircraft would have so materially changed its position the solution would be relatively meaningless.
Although parallel algorithms for dynamic programming problems have been described in the past (see the paper entitled "Parallel Processing Algorithms for the Optimal Control of Non-Linear Dynamic Systems" by R. E. Larson and E. Tse, I.E.E.E. Transactions on Computers, Volume C-22, No. 8, August 1973, pages 777-786), sufficiently adequate methods of organizing the data and passing it between computational elements have not been provided prior to the instant invention to permit the design of a parallel dynamic programming device. That is, the intermediate solutions required for optimum transitions from adjacent cells often requires the same information. The resulting necessity for interprocessor communication in any conventional arrangement has added more complexity and time to dynamic programming device designs to warrant their use.